Super-resolution is a technique used to convert a low resolution image into a higher resolution image. Applications of super-resolution include, for example, improving low resolution images/videos produced from devices such as cell phone cameras or webcams as well as converting normal quality video programs (i.e., NTSC) into higher quality (i.e., HDTV) programs.
Contemporary approaches to image super-resolution may be broadly divided into three categories namely: 1) functional interpolation; 2) reconstruction-based; and 3) learning-based.
Functional interpolation approaches apply an existing function to an image thereby obtaining a processed image. Functional interpretation approaches often blur discontinuities and do not satisfy reconstruction constraint(s). Reconstruction-based approaches generate a high resolution image from a low resolution image sequence. The generated image—while generally meeting reconstruction constraints—does not guarantee contour smoothness. Finally, learning-based approaches use high frequency details from training images to improve a low resolution image.
In a paper entitled “Video Super-Resolution Using Personalized Dictionary”, which appeared in Technical Report, 2005-L163, NEC Laboratories America, Inc., 2005, the authors M. Han, H. Tao, and Y. Gong described a learning-based super-resolution method namely an image hallucination approach consisting of three steps. In step 1, a low frequency image IHl is interpolated from a low resolution image IL. In step 2, a high frequency primitive layer IHp is hallucinated or inferred from IHl based on primal sketch priors. In step 3, reconstruction constraints are enforced thereby producing a final high resolution image IH 
According to the method disclosed, for any low resolution test image IL, a low frequency image IHl is interpolated from IL at first. It is assumed that the primitive layer IHp to be inferred is a linear sum of a number of N high frequency primitives {Bnh, n=1, . . . , N}. The underlying low frequency primitives are {Bnl, n=1, . . . , N} in the IHl. Note that the center of each image patch is on the contours extracted in IHl and the neighboring patches are overlapped.
A straightforward nearest neighbor algorithm is used for this task. For each low frequency primitive Bnl, its normalized {circumflex over (B)}nl is obtained, then the best matched normalized low frequency primitive to {circumflex over (B)}nl in the training data is found and pasted to the corresponding high frequency primitive.
This method tends to encounter two undesirable issues. First, this approach is—in essence—a one-nearest-neighbor (1-NN) approach, which likely leads to an over-fit. When a similar primitive patch pair exists in the training data, the approach generates a very good result. Otherwise, the approach often generates a lot of artifacts.
Second, this method is not scalable. Though an AAN tree algorithm theoretically takes O(log(n)) time to find a best match, it unfortunately takes O(n) space. Cache size of modern computing machines is insignificant as compared to the size of an entire training data set. Consequently, video super resolution employing this method does not run satisfactorily in on-line environments.